
/**
 * Created by IntelliJ IDEA.
 * User: evgeniysorokin
 * Date: 18.09.12
 */

public class Percolation {  //16 bytes object overhead
    
    private int[][] grid; //8 bytes reference + 4N^2 + 24 bytes = 32 + 4N^2
    private WeightedQuickUnionUF quickUnion; //64 + 4N bytes
    private int n; //4 bytes
    
    public Percolation(int N) {
        this.n = N;
        grid = new int[N + 1][N + 1];
        quickUnion = new WeightedQuickUnionUF(N * N);

        for(int i = 1; i <= N; i++)
                grid[i][i] = 0;
    }
    
    private boolean isInBounds(int i, int j) {
        int size = grid.length;
        
        return (i < size && j < size && i != 0 && j != 0);
    }
    
    private int getId(int i, int j) {
        return (i - 1) * (grid.length - 1) + j - 1;
    }
    
    public void open(int i, int j) throws IndexOutOfBoundsException {
        if(!isInBounds(i, j))
            throw new IndexOutOfBoundsException();
                              
        if(grid[i][j] != 1)
            grid[i][j] = 1;

        int id = getId(i, j);
        
        int[] up = new int[]{i - 1, j}, down = new int[]{i + 1, j},
              left = new int[]{i, j - 1}, right = new int[]{i, j + 1};

        if(isInBounds(up[0], up[1]) && isOpen(up[0], up[1])) quickUnion.union(id, getId(up[0], up[1]));
        if(isInBounds(down[0], down[1]) && isOpen(down[0], down[1])) quickUnion.union(id, getId(down[0], down[1]));
        if(isInBounds(left[0], left[1]) && isOpen(left[0], left[1])) quickUnion.union(id, getId(left[0], left[1]));
        if(isInBounds(right[0], right[1]) && isOpen(right[0], right[1])) quickUnion.union(id, getId(right[0], right[1]));
    }
    
    public boolean isOpen(int i, int j) throws IndexOutOfBoundsException {
        if(!isInBounds(i, j))
            throw new IndexOutOfBoundsException();

        return grid[i][j] == 1;
    }

    public boolean isFull(int i, int j) throws IndexOutOfBoundsException {
        if(!isInBounds(i, j))
            throw new IndexOutOfBoundsException();
        
        if(!isOpen(i, j)) return false;

        int id = getId(i, j);

        for(int ii = 0; ii < n; ii++)
            if(quickUnion.connected(id, ii)) return true;
        
        return false;
    }
    
    public boolean percolates() {
        //iterate through bottom row
        for(int i = 1; i <= n; i++)
            if(isFull(n, i)) return true;

        return false;
    }

}